package newcoder_exp.justPractise;

import org.junit.Test;

public class Pra8 {
    //图的n着色问题

    /* 
        回溯条件： g[i][j] * color[i] == color[j]
        图使用邻接矩阵存储
    */

    /**
     * idx: 第idx个顶点进行着色
     * color: 对前面idx-1个节点的着色方案
     * 着色代号为[1...n]
     */
    int[] res = null;
    public boolean dfs(int idx, int[] color, int[][] g) { 
        int n = color.length;
        if (idx == n) {
            //着色完毕
            res = color;
            return true;
        }
        for (int i = 1; i <= n; i++) {
            if (check(idx, g, color, i)) {
                color[idx] = i;
                boolean res = dfs(idx + 1, color, g);
                if (res) return true;
                color[idx] = 0;
            }
        }
        return false;
    }
    //当前顶点是否可以着这个颜色
    public boolean check(int i, int[][] g, int[] color, int c) {
        int n = g.length;
        for (int k = 0; k < n;  k++) {
            if (g[i][k] * color[k] == c)
                return false;
        }
        return true;
    } 

    /* 
        5 4 
        0 1 1 1 0 
        1 0 1 1 1 
        1 1 0 1 0 
        1 1 1 0 1 
        0 1 0 1 0
    */
    public boolean nColors(int[][] g, int n) {
        return dfs(0, new int[g.length], g);
    }

    @Test
    public void test() {
        int[][] nums = new int[5][];
        nums[0] = new int[]{0,1,1,1,0};
        nums[1] = new int[]{1,0, 1, 1, 1};
        nums[2] = new int[]{1, 1, 0, 1, 0};
        nums[3] = new int[]{1,1, 1, 0, 1};
        nums[4] = new int[]{0 ,1, 0, 1, 0};
        System.out.println(nColors(nums, 4));
    }
}
